Modern computer systems often comprise several data storage devices, e.g. an array of independent disk drives. Whenever data storage devices are present in a computer system, data integrity becomes important. To insure data integrity and protect against data loss, parity protection schemes are frequently employed.
In a parity protection scheme, data to be protected are first divided into blocks of data, e.g., blocks of four eight bit words. The data blocks may be further arranged into data groups where each data group may comprise a fixed number of data blocks. For example, each data group may comprise 4 data blocks. The data blocks which comprise a data group may be arranged to form a one dimensional array of data blocks. Thus, a single data group may be viewed as a one dimensional array of data blocks.
Each data block of a particular data group may be stored, e.g., on a different storage device, e.g., a disk drive, with data blocks from several different data groups being stored on a single disk drive. Accordingly, a plurality of data groups, which each comprise a series of data blocks, may be stored in a one dimensional array of data storage devices, e.g., an array of disk drives.
In a one dimensional parity ("1-d parity") protection scheme, which is the simplest form of parity protection, a parity block is generated for each individual data group. The parity block for each data group, which is used to protect against data loss and insure data integrity, may be stored on one of the data storage devices, of the particular array of storage devices, which contains the data group that the parity block is intended to protect.
Thus, in an array of 5 storage devices, 4 data storage devices may, e.g., be used to store data blocks while the fifth data storage device may be used to store parity blocks. For example, when implementing a one dimensional parity scheme, an array of 5 disk drives may be used to store, e.g., 5 data groups where each data group comprises 4 data blocks. In such a case, the first through fourth disk drives in the array of 5 disk drives may each be used to store one data block from each of the 5 data groups., i.e., 5 data blocks per disk drive. The fifth disk drive in the array may be used to store one parity block for each data group, i.e., 5 parity blocks.
The parity block for a particular data group is generated by XORing the contents of each data block, of the particular data group, with the contents of all the other data blocks in the data group to create the parity block for that particular data group. For example, the contents of each data block, in a data group comprising four data blocks, could be XORed with each other to form a single parity block. This parity block may then be stored on a storage device, e.g. the fifth storage device or disk drive in the array of storage devices.
Then, in the event that the data contained in a data block of any one of the data storage devices in the particular data group becomes lost or corrupted, the missing data may be re-generated by XORing the contents of all the intact data storage devices in the particular data group, with the parity block for that data group.
For example, if the contents of the third data block, in the data group comprising four data blocks, became lost or corrupted, the contents of the third data block could be re-generated by XORing the contents of the first, second and fourth data blocks together with the parity block associated with the particular data group.
One known system for generating a parity block, reads words of data from all the storage devices, in an array of storage devices such as disk drives, at the same time and then transmits the data in parallel to a parity generator. The parity generator then XOR's all the words of data together to form a word of the parity block.
This process is repeated for each word of data stored in the data blocks of the data group, until a full parity block is generated from the data blocks. The output of the parity generator is then stored in another data storage device which stores the words of data comprising the parity block for the particular data group.
While the above system processes the data quickly due to the parallel reads from all data blocks in a data group, it doesn't scale easily and becomes impractical to implement for arrays with a large number of data storage devices. For example, in the known system, an array with five data storage devices in a data group, storing eight bit words of data, requires a 40 bit data bus to implement a 1-d parity scheme wherein a word of data from each storage device is transmitted in parallel to the parity generator. However, an array with 20 data storage devices in a data group requires a 160 bit data bus to implement a 1-d parity scheme making the known system impractical due to excessive complexity and implementation cost.
Another disadvantage of the known system is that additional storage devices, containing additional data blocks, may not be added to the system while it is running. Thus, a system shut down is required to change, remove or add storage devices.
In addition to the above known method for implementing a parity generator through the use of hardware, known software products provide for parity generation through the use of software on a host computer. While software implementations of parity generators are the least expensive and most flexible method of implementing such systems, they tend to severely limit system performance. For example, current high performance central processing units ("CPU's") can only perform the parity generation function at several Mb/sec, while a parity generator implemented in hardware can easily perform the parity generation function at speeds exceeding 100 Mb/sec. Thus, such software based parity generators are impractical where rapid system performance is an important consideration.